package newcoder.lx_购物单;

import java.util.Scanner;

/**
 * @Author Mr.wang
 * @Description 链接：https://www.nowcoder.com/questionTerminal/f9c6f980eeec43ef85be20755ddbeaf4?f=discussion
 * 来源：牛客网
 * 输入的第 1 行，为两个正整数，用一个空格隔开：N m
 * （其中 N （ <32000 ）表示总钱数， m （ <60 ）为希望购买物品的个数。）
 * 从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q
 * （其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）
 * @Date 2020-04-11
 */

// 加了限制条件的背包问题

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNextInt()) {
            // 总钱数
            int n = scan.nextInt();
            // 商品个数
            int m = scan.nextInt();
            int[] p = new int[m];// 价格
            int[] v = new int[m];// 价值
            int[] q = new int[m];// 主件或者附件
            for (int i = 0; i < m; i++) {
                // 价格
                p[i] = scan.nextInt();
                // 价值
                v[i] = scan.nextInt() * p[i];
                // 主件或者附件
                q[i] = scan.nextInt();
            }
            System.out.println(getMaxValue(v, p, q, m, n));
        }
    }
//    链接：https://www.nowcoder.com/questionTerminal/f9c6f980eeec43ef85be20755ddbeaf4?f=discussion

    /**
     * @param val    价值
     * @param weight 价格
     * @param q      主件or附件
     * @param n      商品个数
     * @param w      总钱数
     * @return
     */
    public static int getMaxValue(int[] val, int[] weight, int[] q, int n, int w) {
        //初始化动态规划数组
        int[][] dp = new int[n + 1][w + 1];
        //为了便于理解,将dp[i][0]和dp[0][j]均置为0，从1开始计算
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= w; j++) {
                if (q[i - 1] == 0) {  // 主件
                    // 用j这么多钱去买 i 件商品 可以获得最大价值
                    if (weight[i - 1] <= j) {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + val[i - 1]);
                    }
                } else { //附件
                    // 附件的话 加上主件一起算
                    if (weight[i - 1] + weight[q[i - 1]] <= j) {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + val[i - 1]);
                    }
                }
            }
        }
        return dp[n][w];
    }

}
